

/**
 * https://leetcode.cn/problems/unique-paths/
 * 
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
解题思路：
这是一个动态规划的题：
1.因为结果可以拆分为多个子问题的合集，子问题有重复计算性
2.公式是f(i,j)=f(i-1,j)+f(j,i-1)
3.状态边界是f(0,n)=1,f(m,0)=1
时间复杂度=O(n^2)
 @speed 68 ms
 * @param {number} m 行
 * @param {number} n 列
 * @return {number}
 */
var uniquePaths = function(m, n) {
    // 创建个 2维数组, 默认都等于1，其实正常应该只是第一行和列为1（因为第一行和第1列的路径总数总是1，因为题目说只能向右和向下走）
    let arr=new Array(m).fill(0).map(()=>new Array(n).fill(1));
    console.log(arr)
    for(let i=1;i<m;i++){
        for(let j=1;j<n;j++){
            arr[i][j]=arr[i-1][j]+arr[i][j-1];//上面那格+左边那格=当前格的路径总数
            console.log(i,j,arr[i][j])
        }
    }

    console.log(arr)
    return arr[m-1][n-1]
};


console.log(uniquePaths(3,2))